//给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。 
//
// 进阶：你能尝试使用一趟扫描实现吗？ 
//
// 
//
// 示例 1： 
//
// 
//输入：head = [1,2,3,4,5], n = 2
//输出：[1,2,3,5]
// 
//
// 示例 2： 
//
// 
//输入：head = [1], n = 1
//输出：[]
// 
//
// 示例 3： 
//
// 
//输入：head = [1,2], n = 1
//输出：[1]
// 
//
// 
//
// 提示： 
//
// 
// 链表中结点的数目为 sz 
// 1 <= sz <= 30 
// 0 <= Node.val <= 100 
// 1 <= n <= sz 
// 
// Related Topics 链表 双指针 👍 1556 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //设置哑节点，方便只有一个元素时删除节点。
        ListNode dummy = new ListNode(0, head);
        int len = 0;
        ListNode cur = head;
        //统计链表长度
        while (cur != null){
            len++;
            cur = cur.next;
        }
        int i = 1;
        cur = dummy;//cur从哑节点开始
        //从哑节点开始遍历，链表长度为n+1。最后cur指向倒数n+1个位置
        while (cur != null && i < len + 1 - n){
            i++;
            cur = cur.next;
        }
        //删除第n个节点
        cur.next = cur.next.next;
        return dummy.next;


//        ListNode dummy = new ListNode(0, head);
//        ListNode left = dummy, right = dummy;
//        int count = 0;
//        //right比left先走n + 1步
//        //当right指向null时，left指向倒数n + 1个元素
//        while(count <= n){
//            count++;
//            right = right.next;
//        }
//        while (right != null){
//            left = left.next;
//            right = right.next;
//        }
//
//        left.next = left.next.next;
//        return dummy.next;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
